0908. 最小差值 I【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，和一个整数 k。

在一个操作中，您可以选择 0 <= i < nums.length 的任何索引 i。将 nums[i] 改为 nums[i] + x，其中 x 是一个范围为 [-k, k] 的任意整数。对于每个索引 i，最多只能应用一次此操作。

nums 的分数是 nums 中最大和最小元素的差值。

在对 nums 中的每个索引最多应用一次上述操作后，返回 nums 的最低分数。

---

示例 1：

输入：nums = [1], k = 0
输出：0

解释：
分数是 max(nums) - min(nums) = 1 - 1 = 0。

---

示例 2：

输入：nums = [0,10], k = 2
输出：6

解释：
将 nums 改为 [2,8]。分数是 max(nums) - min(nums) = 8 - 2 = 6。

---

示例 3：

输入：nums = [1,3,6], k = 3
输出：0

解释：
将 nums 改为 [4,4,4]。分数是 max(nums) - min(nums) = 4 - 4 = 0。

---

提示：

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^4
• 0 <= k <= 10^4

2. 🎯 s.1 - 暴力解法

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestRangeI = function (nums, k) {
  let minVal = Infinity
  let maxVal = -Infinity
  for (let i = 0; i < nums.length; i++) {
    const v = nums[i]
    if (v < minVal) minVal = v
    if (v > maxVal) maxVal = v
  }
  const reduced = maxVal - minVal - 2 * k
  return reduced > 0 ? reduced : 0
}

• 时间复杂度：$O(n)$，一次遍历求最大值与最小值
• 空间复杂度：$O(1)$

算法思路：

• 操作允许每个元素在区间 [−k, k] 内调整一次，最大值最多降 k，最小值最多升 k
• 原始差值为 max − min，最多可缩减为 max − min − 2k
• 若缩减后为负或零，则可把数组所有值“拉近”到同一值，答案为 0；否则返回 max − min − 2k